Termination w.r.t. Q proof of /tmp/tmpE5zwMy/logarithm.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

Q is empty.

↳ QTRS

  ↳ AAECC Innermost

Q restricted rewrite system:
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

Q is empty.

We have applied [19,8] to switch to innermost. The TRS R 1 is

half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
half(0) → 0
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError

The TRS R 2 is

f → g
f → h

The signature Sigma is {f, g, h}

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y) → HALF(x)
LOGITER(x, y) → LE(s(0), x)
LOGARITHM(x) → LOGITER(x, 0)
HALF(s(s(x))) → HALF(x)
LOGITER(x, y) → LE(s(s(0)), x)
INC(s(x)) → INC(x)
LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
IF(true, true, x, y) → LOGITER(x, y)
LOGITER(x, y) → INC(y)
LE(s(x), s(y)) → LE(x, y)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y) → HALF(x)
LOGITER(x, y) → LE(s(0), x)
LOGARITHM(x) → LOGITER(x, 0)
HALF(s(s(x))) → HALF(x)
LOGITER(x, y) → LE(s(s(0)), x)
INC(s(x)) → INC(x)
LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
IF(true, true, x, y) → LOGITER(x, y)
LOGITER(x, y) → INC(y)
LE(s(x), s(y)) → LE(x, y)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 4 SCCs with 5 less nodes.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ UsableRulesProof

              ↳ QDP

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

INC(s(x)) → INC(x)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

              ↳ QDP

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

INC(s(x)) → INC(x)

R is empty.
The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ QDPSizeChangeProof

              ↳ QDP

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

INC(s(x)) → INC(x)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

INC(s(x)) → INC(x)
The graph contains the following edges 1 > 1

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

LE(s(x), s(y)) → LE(x, y)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

LE(s(x), s(y)) → LE(x, y)

R is empty.
The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ QDPSizeChangeProof

              ↳ QDP

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

LE(s(x), s(y)) → LE(x, y)

From the DPs we obtained the following set of size-change graphs:

LE(s(x), s(y)) → LE(x, y)
The graph contains the following edges 1 > 1, 2 > 2

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)

R is empty.
The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ QDPSizeChangeProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)

From the DPs we obtained the following set of size-change graphs:

HALF(s(s(x))) → HALF(x)
The graph contains the following edges 1 > 1

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
inc(s(x)) → s(inc(x))
inc(0) → s(0)
logarithm(x) → logIter(x, 0)
logIter(x, y) → if(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
if(false, b, x, y) → logZeroError
if(true, false, x, s(y)) → y
if(true, true, x, y) → logIter(x, y)
f → g
f → h

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)
logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

logarithm(x0)
logIter(x0, x1)
if(false, x0, x1, x2)
if(true, false, x0, s(x1))
if(true, true, x0, x1)
f

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
In the following pairs the term without variables s(s(0)) is replaced by the fresh variable x_removed.
Pair: LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y))
Positions in right side of the pair:

[1,0]

The new variable was added to all pairs as a new argument[13].

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                          ↳ QDP

                        ↳ RemovalProof

                        ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y, x_removed) → IF(le(s(0), x), le(x_removed, x), half(x), inc(y), x_removed)
IF(true, true, x, y, x_removed) → LOGITER(x, y, x_removed)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

[1,0]

The new variable was added to all pairs as a new argument[13].

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                          ↳ QDP

                        ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

LOGITER(x, y, x_removed) → IF(le(s(0), x), le(x_removed, x), half(x), inc(y), x_removed)
IF(true, true, x, y, x_removed) → LOGITER(x, y, x_removed)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule LOGITER(x, y) → IF(le(s(0), x), le(s(s(0)), x), half(x), inc(y)) at position [0] we obtained the following new rules:

LOGITER(s(x1), y1) → IF(le(0, x1), le(s(s(0)), s(x1)), half(s(x1)), inc(y1))
LOGITER(0, y1) → IF(false, le(s(s(0)), 0), half(0), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(0, y1) → IF(false, le(s(s(0)), 0), half(0), inc(y1))
LOGITER(s(x1), y1) → IF(le(0, x1), le(s(s(0)), s(x1)), half(s(x1)), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

Q DP problem:
The TRS P consists of the following rules:

IF(true, true, x, y) → LOGITER(x, y)
LOGITER(s(x1), y1) → IF(le(0, x1), le(s(s(0)), s(x1)), half(s(x1)), inc(y1))

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By rewriting [15] the rule LOGITER(s(x1), y1) → IF(le(0, x1), le(s(s(0)), s(x1)), half(s(x1)), inc(y1)) at position [0] we obtained the following new rules:

LOGITER(s(x1), y1) → IF(true, le(s(s(0)), s(x1)), half(s(x1)), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(x1), y1) → IF(true, le(s(s(0)), s(x1)), half(s(x1)), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By rewriting [15] the rule LOGITER(s(x1), y1) → IF(true, le(s(s(0)), s(x1)), half(s(x1)), inc(y1)) at position [1] we obtained the following new rules:

LOGITER(s(x1), y1) → IF(true, le(s(0), x1), half(s(x1)), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(x1), y1) → IF(true, le(s(0), x1), half(s(x1)), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule LOGITER(s(x1), y1) → IF(true, le(s(0), x1), half(s(x1)), inc(y1)) at position [1] we obtained the following new rules:

LOGITER(s(0), y1) → IF(true, false, half(s(0)), inc(y1))
LOGITER(s(s(x1)), y1) → IF(true, le(0, x1), half(s(s(x1))), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, le(0, x1), half(s(s(x1))), inc(y1))
LOGITER(s(0), y1) → IF(true, false, half(s(0)), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, le(0, x1), half(s(s(x1))), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
le(0, y) → true

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, le(0, x1), half(s(s(x1))), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(0, y) → true
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By rewriting [15] the rule LOGITER(s(s(x1)), y1) → IF(true, le(0, x1), half(s(s(x1))), inc(y1)) at position [1] we obtained the following new rules:

LOGITER(s(s(x1)), y1) → IF(true, true, half(s(s(x1))), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, true, half(s(s(x1))), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

le(0, y) → true
half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, true, half(s(s(x1))), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, true, half(s(s(x1))), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By rewriting [15] the rule LOGITER(s(s(x1)), y1) → IF(true, true, half(s(s(x1))), inc(y1)) at position [2] we obtained the following new rules:

LOGITER(s(s(x1)), y1) → IF(true, true, s(half(x1)), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, true, s(half(x1)), inc(y1))
IF(true, true, x, y) → LOGITER(x, y)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By instantiating [15] the rule IF(true, true, x, y) → LOGITER(x, y) we obtained the following new rules:

IF(true, true, s(y_0), y_1) → LOGITER(s(y_0), y_1)

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

                                                                      ↳ QDP

                                                                        ↳ ForwardInstantiation

Q DP problem:
The TRS P consists of the following rules:

IF(true, true, s(y_0), y_1) → LOGITER(s(y_0), y_1)
LOGITER(s(s(x1)), y1) → IF(true, true, s(half(x1)), inc(y1))

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By forward instantiating [14] the rule IF(true, true, s(y_0), y_1) → LOGITER(s(y_0), y_1) we obtained the following new rules:

IF(true, true, s(s(y_0)), x1) → LOGITER(s(s(y_0)), x1)

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

                                                                      ↳ QDP

                                                                        ↳ ForwardInstantiation

                                                                          ↳ QDP

                                                                            ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(x1)), y1) → IF(true, true, s(half(x1)), inc(y1))
IF(true, true, s(s(y_0)), x1) → LOGITER(s(s(y_0)), x1)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule LOGITER(s(s(x1)), y1) → IF(true, true, s(half(x1)), inc(y1)) at position [2,0] we obtained the following new rules:

LOGITER(s(s(s(s(x0)))), y1) → IF(true, true, s(s(half(x0))), inc(y1))
LOGITER(s(s(0)), y1) → IF(true, true, s(0), inc(y1))
LOGITER(s(s(s(0))), y1) → IF(true, true, s(0), inc(y1))

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

                                                                      ↳ QDP

                                                                        ↳ ForwardInstantiation

                                                                          ↳ QDP

                                                                            ↳ Narrowing

                                                                              ↳ QDP

                                                                                ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(s(s(x0)))), y1) → IF(true, true, s(s(half(x0))), inc(y1))
LOGITER(s(s(0)), y1) → IF(true, true, s(0), inc(y1))
LOGITER(s(s(s(0))), y1) → IF(true, true, s(0), inc(y1))
IF(true, true, s(s(y_0)), x1) → LOGITER(s(s(y_0)), x1)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 2 less nodes.

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

                                                                      ↳ QDP

                                                                        ↳ ForwardInstantiation

                                                                          ↳ QDP

                                                                            ↳ Narrowing

                                                                              ↳ QDP

                                                                                ↳ DependencyGraphProof

                                                                                  ↳ QDP

                                                                                    ↳ RuleRemovalProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(s(s(x0)))), y1) → IF(true, true, s(s(half(x0))), inc(y1))
IF(true, true, s(s(y_0)), x1) → LOGITER(s(s(y_0)), x1)

The TRS R consists of the following rules:

half(s(s(x))) → s(half(x))
inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0
half(s(0)) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
By using the rule removal processor [15] with the following polynomial ordering [25], at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
Strictly oriented dependency pairs:

IF(true, true, s(s(y_0)), x1) → LOGITER(s(s(y_0)), x1)

Strictly oriented rules of the TRS R:

half(s(s(x))) → s(half(x))
half(s(0)) → 0

Used ordering: POLO with Polynomial interpretation [25]:

POL(0) = 0
POL(IF(x₁, x₂, x₃, x₄)) = 2 + 2·x₁ + 2·x₂ + 2·x₃ + 2·x₄
POL(LOGITER(x₁, x₂)) = 2 + 2·x₁ + 2·x₂
POL(half(x₁)) = x₁
POL(inc(x₁)) = 2 + x₁
POL(s(x₁)) = 2 + x₁
POL(true) = 1

↳ QTRS

  ↳ AAECC Innermost

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

              ↳ QDP

              ↳ QDP

                ↳ UsableRulesProof

                  ↳ QDP

                    ↳ QReductionProof

                      ↳ QDP

                        ↳ RemovalProof

                        ↳ RemovalProof

                        ↳ Narrowing

                          ↳ QDP

                            ↳ DependencyGraphProof

                              ↳ QDP

                                ↳ Rewriting

                                  ↳ QDP

                                    ↳ Rewriting

                                      ↳ QDP

                                        ↳ Narrowing

                                          ↳ QDP

                                            ↳ DependencyGraphProof

                                              ↳ QDP

                                                ↳ UsableRulesProof

                                                  ↳ QDP

                                                    ↳ Rewriting

                                                      ↳ QDP

                                                        ↳ UsableRulesProof

                                                          ↳ QDP

                                                            ↳ QReductionProof

                                                              ↳ QDP

                                                                ↳ Rewriting

                                                                  ↳ QDP

                                                                    ↳ Instantiation

                                                                      ↳ QDP

                                                                        ↳ ForwardInstantiation

                                                                          ↳ QDP

                                                                            ↳ Narrowing

                                                                              ↳ QDP

                                                                                ↳ DependencyGraphProof

                                                                                  ↳ QDP

                                                                                    ↳ RuleRemovalProof

                                                                                      ↳ QDP

                                                                                        ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

LOGITER(s(s(s(s(x0)))), y1) → IF(true, true, s(s(half(x0))), inc(y1))

The TRS R consists of the following rules:

inc(s(x)) → s(inc(x))
inc(0) → s(0)
half(0) → 0

The set Q consists of the following terms:

half(0)
half(s(0))
half(s(s(x0)))
inc(s(x0))
inc(0)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 0 SCCs with 1 less node.